package com.leetcode.partition1;

import com.leetcode.common.ListNode;

/**
 * @author `RKC`
 * @date 2021/9/10 19:36
 */
public class LC19删除链表的倒数第N个结点 {

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        return doubleIndex(head, n);
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2));
        head = removeNthFromEnd(head, 2);
        while (head != null) {
            System.out.printf("%3d, ", head.val);
            head = head.next;
        }
    }

    private static ListNode doubleIndex(ListNode head, int n) {
        if (head.next == null && n == 1) return null;
        ListNode dummy = new ListNode(-1, head);
        ListNode slow = dummy, fast = dummy;
        //让左指针和右指针相差n+1
        while (n-- > 0) fast = fast.next;
        ListNode prev = null;            //slow的上一个节点
        //同时遍历左右指针，直到右指针指向最后一个元素，此时左指针指向被删除节点的前一个节点
        while (fast != null) {
            prev = slow;
            fast = fast.next;
            slow = slow.next;
        }
        prev.next = slow.next;
        return dummy.next;
    }
}
